package com.cande.loki.exercise.algorithm;

/**
 * 背包问题
 */
public class DP {
    public static void main(String[] args) {
        int W = 50;  // 背包容量
        int[] weights = {10, 20, 30};  // 物品重量
        int[] values = {60, 100, 120}; // 物品价值
        int n = weights.length;  // 物品数量

        System.out.println("Max value: " + knapsack(W, weights, values, n));
    }

        // 返回最大价值
        public static int knapsack(int W, int[] weights, int[] values, int n) {
            // 创建二维数组 dp，dp[i][j] 表示前 i 件物品，容量为 j 时的最大价值
            int[][] dp = new int[n + 1][W + 1];

            // 遍历每件物品
            for (int i = 1; i <= n; i++) {
                // 遍历背包容量
                for (int j = 0; j <= W; j++) {
                    if (j >= weights[i - 1]) {
                        // 选或不选第 i 件物品，取最大值
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                    } else {
                        // 容量不足，无法选择该物品
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }

            // 返回最大价值
            return dp[n][W];
        }
}
